from typing import List


class Solution:
    # 思路：线段树

    class _Node:
        def __init__(self, idx):
            self.idx = idx
            self.n = 1  # 树包含的节点数（包含自身）
            self.val = 0  # 树自身的值
            self.lazy = 0  # 树尚未计算的值
            self.father = 0  # 树的父节点
            self.children = set()  # 树的子节点列表

    def __init__(self):
        self.tree = []

    def bonus(self, n: int, leadership: List[List[int]], operations: List[List[int]]) -> List[int]:
        # 构造线段树节点
        self.tree = [self._Node(i) for i in range(n + 1)]

        # 构造线段树的领导关系
        for a, b in leadership:
            self.tree[a].children.add(b)
            self.tree[b].father = a

        # 计算树中每个节点包含的节点数量
        self.dfs(1)

        ans = []

        # 执行操作
        for operation in operations:
            # 第1种操作：给团队的一个成员（也可以是负责人）发一定数量的LeetCoin
            if operation[0] == 1:
                now, value = operation[1], operation[2]
                # 将当前新增值不断向上传递，直到传递到负责人
                while now > 0:
                    self.tree[now].val += value
                    now = self.tree[now].father

            # 第2种操作：给团队的一个成员（也可以是负责人），以及他/她管理的所有人（即他/她的下属、他/她下属的下属，……），发一定数量的LeetCoin
            elif operation[0] == 2:
                # 依据当前成员包含的节点数量，计算增加总量
                now, value = operation[1], self.tree[operation[1]].n * operation[2]
                # 将当前新增值不断向上传递，直到传递到负责人（同样更新了当前节点）
                while now > 0:
                    self.tree[now].val += value
                    now = self.tree[now].father
                # 将当前新值需要向下传递的记录到lazy中
                self.tree[operation[1]].lazy += operation[2]

            # 第3种操作：查询某一个成员（也可以是负责人），以及他/她管理的所有人被发到的LeetCoin之和
            else:
                # 计算所有父节点的列表
                stack = []
                now = operation[1]
                while now > 0:
                    stack.append(now)
                    now = self.tree[now].father
                # 计算所有父节点的lazy属性
                while stack:
                    now = stack.pop()
                    if self.tree[now].lazy > 0:
                        for child in self.tree[now].children:
                            self.tree[child].val += self.tree[child].n * self.tree[now].lazy
                            self.tree[child].lazy += self.tree[now].lazy
                        self.tree[now].lazy = 0
                # print(operation, "->", self.tree[operation[1]].val % 1000000007)
                ans.append(self.tree[operation[1]].val % 1000000007)

        return ans

    def dfs(self, now):
        """计算线段树中每个节点包含的子节点数量"""
        self.tree[now].n = 1
        for child in self.tree[now].children:
            self.tree[now].n += self.dfs(child)
        return self.tree[now].n


if __name__ == "__main__":
    # [650, 665]
    print(Solution().bonus(n=6,
                           leadership=[[1, 2], [1, 6], [2, 3], [2, 5], [1, 4]],
                           operations=[[1, 1, 500], [2, 2, 50], [3, 1], [2, 6, 15], [3, 1]]
                           ))

    # [53, 53, 0, 79, 0, 0, 315, 315, 577, 2, 750, 750, 0, 750, 57, 2245, 94, 19, 111, 406, 37, 0, 2646, 163, 2726, 558, 0,
    # 2807, 2, 163, 2325, 2325, 2325, 2359, 2388, 243, 3073, 39, 3181, 11, 362, 390, 390, 6724, 1, 421, 0, 440, 440, 475, 0,
    # 3387, 7267, 3408, 514, 7320, 554, 7409, 7438, 3605, 3605, 7848, 3648, 49, 3777, 8202, 2, 0, 8214, 3958, 0, 3958, 8528,
    # 4047, 8651, 722, 5, 4083, 8682, 8990, 2, 9569, 5278, 10635, 5297, 5297, 33, 5339, 10945, 73, 51, 761, 86, 794, 11471,
    # 5435, 794, 5637, 53, 63, 881, 5805, 898, 5805, 12120, 5814, 12525, 1244, 1244, 5814, 5917, 1244, 74, 50, 1317, 1275,
    # 5971, 1275, 6028, 13261, 1333, 74, 1341, 1384, 13565, 13633, 6158, 1447, 1447, 1447, 6205, 6263, 28, 14285, 14285, 21,
    # 1620, 1661, 6379, 6379, 6379, 177, 76, 15068, 6401, 6401]
    print(Solution().bonus(
        n=450,
        leadership=[[1, 152], [1, 203], [1, 218], [1, 441], [1, 370], [1, 173], [152, 28], [152, 85],
                    [152, 269], [152, 263], [152, 333], [152, 383], [152, 144], [152, 179], [203, 382],
                    [203, 245], [203, 21], [203, 436], [203, 174], [203, 79], [203, 76], [203, 348], [203, 373],
                    [203, 414], [218, 290], [218, 392], [218, 365], [218, 314], [218, 131], [218, 304],
                    [218, 4], [441, 407], [441, 367], [441, 60], [441, 108], [441, 10], [441, 192], [441, 315],
                    [441, 51], [441, 115], [441, 295], [370, 447], [370, 390], [370, 123], [370, 409],
                    [370, 296], [370, 67], [370, 432], [370, 387], [370, 220], [370, 375], [173, 204],
                    [173, 286], [173, 117], [173, 119], [173, 443], [173, 162], [173, 26], [173, 258],
                    [28, 137], [28, 133], [28, 442], [28, 148], [28, 186], [28, 311], [28, 182], [28, 153],
                    [85, 317], [85, 105], [269, 240], [269, 12], [269, 125], [269, 395], [269, 412], [269, 168],
                    [269, 257], [269, 342], [263, 408], [263, 96], [263, 420], [263, 180], [263, 5], [263, 430],
                    [263, 405], [333, 103], [333, 415], [333, 328], [333, 92], [333, 261], [383, 58],
                    [383, 349], [383, 9], [383, 65], [383, 16], [144, 446], [144, 448], [144, 200], [144, 77],
                    [144, 73], [179, 197], [179, 210], [179, 37], [179, 127], [179, 380], [179, 371], [179, 33],
                    [179, 62], [179, 205], [382, 323], [382, 110], [382, 91], [382, 259], [245, 81], [245, 111],
                    [245, 158], [245, 272], [245, 87], [245, 121], [21, 161], [21, 274], [21, 363], [21, 284],
                    [21, 195], [21, 202], [21, 7], [436, 439], [436, 381], [436, 99], [436, 308], [436, 22],
                    [436, 260], [436, 437], [436, 241], [436, 324], [174, 270], [174, 386], [174, 83],
                    [79, 388], [79, 227], [79, 113], [79, 70], [79, 142], [76, 32], [76, 346], [76, 426],
                    [76, 156], [348, 13], [348, 64], [348, 47], [348, 250], [348, 267], [348, 343], [348, 208],
                    [348, 262], [348, 291], [348, 338], [373, 25], [373, 438], [373, 42], [373, 353], [373, 20],
                    [373, 374], [373, 355], [373, 337], [414, 126], [414, 19], [414, 176], [414, 299],
                    [414, 264], [414, 358], [414, 359], [414, 71], [414, 236], [290, 104], [290, 320],
                    [290, 154], [290, 216], [290, 112], [290, 385], [290, 122], [392, 194], [392, 171],
                    [392, 35], [392, 368], [392, 82], [392, 184], [392, 427], [365, 301], [365, 114],
                    [365, 232], [365, 31], [365, 128], [365, 116], [365, 147], [314, 175], [314, 159],
                    [314, 86], [314, 297], [314, 139], [314, 55], [314, 8], [314, 107], [314, 102], [314, 306],
                    [131, 253], [304, 431], [304, 206], [4, 331], [4, 189], [4, 277], [4, 289], [4, 404],
                    [4, 347], [4, 66], [4, 95], [4, 397], [4, 318], [407, 398], [367, 98], [367, 230],
                    [367, 411], [367, 78], [367, 273], [367, 43], [60, 249], [60, 155], [60, 215], [60, 434],
                    [60, 199], [108, 61], [108, 444], [108, 422], [108, 207], [108, 243], [10, 251], [10, 254],
                    [10, 421], [10, 282], [192, 403], [192, 307], [315, 134], [315, 350], [315, 276],
                    [315, 396], [315, 106], [315, 417], [315, 266], [315, 248], [51, 223], [51, 172], [51, 136],
                    [51, 429], [51, 293], [51, 178], [51, 312], [51, 321], [51, 80], [115, 90], [115, 345],
                    [115, 191], [115, 410], [295, 201], [295, 34], [295, 334], [295, 151], [295, 400],
                    [295, 275], [295, 181], [295, 310], [295, 424], [447, 124], [390, 402], [390, 339],
                    [390, 231], [390, 423], [390, 188], [390, 17], [123, 389], [123, 278], [123, 132],
                    [409, 362], [409, 135], [409, 287], [409, 242], [409, 157], [409, 384], [409, 183],
                    [409, 63], [409, 309], [296, 224], [67, 190], [67, 57], [432, 401], [432, 109], [432, 298],
                    [432, 319], [432, 435], [432, 149], [432, 101], [432, 30], [432, 237], [387, 285],
                    [387, 40], [220, 361], [220, 143], [220, 280], [220, 52], [220, 75], [220, 88], [220, 3],
                    [220, 146], [220, 100], [375, 59], [375, 120], [375, 53], [375, 336], [375, 419], [375, 36],
                    [204, 226], [204, 279], [286, 68], [117, 212], [117, 167], [117, 48], [117, 268], [117, 93],
                    [119, 89], [119, 24], [119, 234], [119, 39], [119, 335], [119, 372], [119, 233], [119, 352],
                    [119, 163], [119, 187], [443, 221], [443, 225], [443, 326], [443, 213], [443, 351],
                    [162, 292], [26, 354], [258, 329], [258, 94], [258, 393], [258, 18], [258, 138], [258, 217],
                    [258, 327], [137, 239], [137, 196], [137, 41], [137, 244], [137, 340], [137, 118],
                    [137, 198], [137, 185], [137, 235], [133, 209], [442, 391], [442, 366], [442, 44],
                    [442, 433], [442, 14], [442, 302], [442, 6], [148, 425], [148, 252], [148, 166], [148, 222],
                    [148, 56], [186, 303], [186, 376], [311, 344], [311, 160], [182, 27], [182, 54], [182, 364],
                    [182, 11], [182, 246], [182, 69], [182, 165], [182, 256], [182, 169], [182, 29], [153, 416],
                    [153, 141], [153, 440], [153, 170], [153, 449], [317, 265], [317, 46], [317, 214],
                    [317, 325], [317, 145], [317, 300], [105, 378], [105, 322], [105, 49], [240, 313],
                    [240, 450], [240, 377], [240, 228], [240, 413], [240, 281], [240, 288], [240, 330],
                    [240, 129], [12, 38], [12, 219], [12, 15], [125, 72], [125, 238], [125, 406], [125, 45],
                    [395, 140], [395, 97], [395, 247], [395, 369], [412, 356], [412, 418], [412, 316],
                    [412, 305], [412, 357], [412, 379], [412, 193], [412, 23], [168, 255], [168, 2], [168, 399],
                    [168, 360], [168, 428], [168, 229], [257, 150], [257, 130], [257, 50], [257, 211],
                    [257, 445], [257, 394], [257, 177], [342, 164], [342, 271], [342, 341], [342, 294],
                    [342, 74], [342, 283], [342, 332], [342, 84]],
        operations=[[1, 392, 24], [1, 108, 10], [2, 34, 11], [2, 328, 10], [1, 302, 6], [1, 384, 27],
                    [2, 420, 30], [1, 184, 7], [2, 328, 7], [3, 152], [3, 152], [2, 205, 8], [2, 173, 2],
                    [1, 432, 49], [3, 203], [1, 37, 18], [3, 152], [2, 77, 26], [3, 313], [3, 98], [3, 1],
                    [3, 1], [1, 378, 50], [1, 179, 32], [2, 123, 45], [3, 1], [2, 236, 2], [2, 35, 49],
                    [1, 55, 38], [3, 203], [1, 436, 36], [2, 130, 1], [2, 337, 19], [1, 27, 28], [3, 1], [3, 1],
                    [3, 363], [3, 1], [1, 186, 13], [1, 415, 29], [2, 369, 1], [1, 320, 33], [1, 256, 31],
                    [2, 278, 13], [3, 203], [1, 150, 31], [1, 434, 50], [2, 97, 29], [2, 441, 19], [2, 96, 8],
                    [2, 253, 41], [3, 1], [1, 263, 45], [1, 270, 37], [3, 203], [2, 353, 15], [2, 284, 2],
                    [1, 420, 3], [2, 435, 22], [2, 282, 21], [2, 292, 12], [3, 424], [3, 203], [3, 152],
                    [2, 284, 4], [2, 427, 40], [1, 384, 49], [2, 126, 48], [3, 174], [1, 326, 42], [1, 408, 48],
                    [2, 378, 13], [3, 189], [3, 1], [1, 72, 50], [1, 137, 24], [2, 95, 6], [3, 203], [3, 1],
                    [1, 360, 17], [3, 152], [1, 66, 3], [3, 298], [2, 68, 10], [2, 252, 27], [1, 146, 10],
                    [1, 384, 14], [3, 1], [2, 269, 29], [1, 411, 31], [1, 199, 4], [1, 325, 20], [3, 351],
                    [2, 390, 21], [3, 203], [2, 54, 38], [1, 224, 40], [1, 99, 46], [3, 152], [3, 152],
                    [3, 152], [1, 322, 34], [3, 152], [1, 352, 29], [1, 333, 29], [1, 404, 15], [2, 372, 39],
                    [3, 152], [2, 171, 39], [2, 241, 34], [3, 203], [1, 280, 5], [1, 428, 35], [2, 365, 11],
                    [2, 215, 40], [2, 299, 3], [2, 202, 2], [1, 373, 31], [2, 443, 1], [2, 78, 32], [1, 278, 5],
                    [1, 123, 1], [2, 28, 13], [1, 249, 23], [1, 249, 40], [1, 52, 2], [3, 152], [2, 296, 22],
                    [1, 349, 10], [1, 153, 25], [2, 163, 18], [1, 8, 28], [2, 346, 41], [1, 72, 2],
                    [2, 341, 36], [1, 427, 20], [1, 159, 5], [2, 210, 1], [1, 409, 44], [1, 129, 34], [3, 171],
                    [2, 106, 25], [3, 152], [3, 301], [2, 386, 42], [1, 230, 39], [2, 402, 47], [1, 432, 43],
                    [1, 31, 22], [1, 297, 24], [1, 256, 28], [2, 5, 1], [2, 321, 10], [2, 131, 21], [3, 203],
                    [1, 241, 19], [1, 121, 9], [3, 203], [1, 399, 21], [3, 203], [2, 92, 47], [3, 1],
                    [1, 182, 12], [1, 441, 26], [2, 78, 31], [2, 351, 41], [1, 66, 33], [1, 421, 2],
                    [2, 343, 31], [3, 5], [1, 85, 15], [2, 321, 2], [2, 366, 21], [3, 203], [2, 133, 15],
                    [1, 205, 31], [1, 323, 19], [1, 135, 21], [3, 227], [1, 143, 35], [3, 203], [3, 203],
                    [2, 401, 12], [2, 355, 35], [1, 136, 43], [3, 203], [3, 57], [2, 359, 22], [3, 152],
                    [2, 27, 4], [2, 216, 31], [1, 171, 46], [3, 1], [1, 146, 14], [2, 323, 17], [2, 244, 17],
                    [3, 152], [3, 203], [2, 351, 5], [3, 1], [2, 255, 13], [1, 41, 12], [1, 111, 40],
                    [1, 153, 12], [3, 203], [1, 255, 12], [3, 1], [1, 92, 29], [3, 1], [1, 369, 4],
                    [2, 209, 27], [1, 225, 34], [1, 336, 45], [1, 224, 21], [2, 257, 6], [2, 219, 40],
                    [1, 113, 29], [2, 274, 40], [3, 152], [2, 171, 5], [2, 318, 30], [2, 142, 5], [1, 254, 41],
                    [2, 132, 41], [3, 152], [3, 1], [1, 356, 43], [3, 152], [1, 270, 16], [3, 245],
                    [1, 259, 28], [1, 71, 44], [1, 32, 6], [2, 427, 28], [1, 417, 31], [2, 311, 43], [3, 152],
                    [2, 6, 29], [3, 1], [3, 48], [1, 402, 12], [3, 197], [3, 1], [2, 442, 19], [3, 152],
                    [3, 324], [2, 275, 18], [3, 152], [1, 283, 27], [1, 317, 39], [1, 292, 26], [1, 143, 29],
                    [2, 141, 23], [3, 1], [3, 152], [1, 41, 36], [2, 39, 41], [2, 151, 46], [3, 1], [3, 203],
                    [3, 280], [2, 400, 31], [3, 152], [3, 1], [2, 342, 20], [2, 419, 7], [2, 18, 39],
                    [1, 153, 35], [1, 332, 47], [3, 1], [2, 257, 50], [2, 3, 36], [1, 35, 23], [2, 213, 22],
                    [2, 116, 50], [1, 67, 6], [3, 268], [2, 68, 42], [3, 1], [1, 179, 19], [2, 192, 31],
                    [2, 233, 44], [2, 381, 26], [2, 170, 36], [2, 442, 41], [1, 263, 25], [2, 117, 49],
                    [1, 362, 45], [1, 401, 19], [1, 367, 12], [2, 137, 7], [1, 369, 19], [1, 144, 36], [3, 152],
                    [3, 1], [1, 142, 3], [1, 130, 19], [3, 152], [2, 276, 11], [2, 353, 6], [1, 234, 46],
                    [3, 152], [1, 205, 3], [1, 117, 24], [1, 11, 17], [2, 444, 46], [1, 51, 3], [1, 341, 22],
                    [1, 310, 9], [1, 22, 4], [3, 420], [1, 275, 16], [3, 152], [2, 387, 17], [1, 265, 30],
                    [3, 1],
                    [3, 14],
                    [1, 85, 4], [3, 167], [1, 116, 14], [3, 203], [1, 419, 6], [2, 380, 8],
                    [2, 176, 33], [3, 132], [2, 258, 33], [1, 398, 45], [2, 278, 41], [2, 268, 29], [1, 27, 29],
                    [2, 254, 29], [3, 203], [1, 28, 24], [3, 1], [1, 164, 1], [3, 152], [1, 430, 24],
                    [2, 303, 32], [3, 203], [1, 394, 1], [1, 167, 26], [2, 309, 17], [2, 163, 44], [2, 328, 10],
                    [1, 52, 7], [2, 447, 14], [1, 283, 45], [2, 344, 21], [2, 91, 2], [1, 413, 32], [2, 73, 34],
                    [2, 80, 26], [1, 169, 3], [3, 152], [1, 251, 11], [2, 130, 11], [1, 261, 6], [2, 317, 14],
                    [1, 236, 49], [1, 398, 5], [1, 180, 11], [3, 270], [2, 330, 42], [3, 378], [2, 146, 6],
                    [2, 284, 27], [1, 382, 9], [3, 203], [2, 262, 17], [3, 152], [3, 203], [1, 402, 4],
                    [3, 152], [3, 1], [2, 325, 9], [2, 435, 10], [1, 353, 37], [2, 161, 15], [2, 345, 11],
                    [1, 190, 29], [2, 79, 49], [3, 152], [3, 1], [3, 203], [3, 203], [3, 152], [2, 179, 7],
                    [1, 424, 43], [2, 145, 33], [3, 152], [1, 331, 25], [2, 48, 3], [3, 203], [1, 354, 38],
                    [1, 56, 35], [3, 27], [1, 404, 17], [1, 258, 17], [1, 92, 19], [3, 399], [2, 86, 31],
                    [3, 173], [2, 267, 31], [3, 203], [2, 319, 31], [2, 232, 28], [2, 131, 35], [3, 152],
                    [1, 120, 45], [2, 268, 16], [2, 402, 22], [3, 203], [1, 135, 8], [2, 377, 4], [1, 185, 6],
                    [2, 377, 47], [1, 315, 40], [3, 152], [1, 284, 17], [1, 404, 38], [2, 296, 1], [3, 1],
                    [1, 126, 41], [3, 203], [2, 158, 8], [2, 4, 1], [2, 44, 9], [2, 408, 9], [3, 18],
                    [2, 141, 31], [3, 203], [2, 31, 43], [1, 345, 12], [2, 121, 43], [2, 3, 38], [1, 310, 15],
                    [3, 203], [1, 270, 44], [3, 1], [1, 309, 24], [2, 445, 44], [3, 1], [1, 269, 37], [3, 152],
                    [1, 239, 35], [2, 48, 30], [1, 150, 12], [1, 436, 19], [3, 203], [3, 203], [2, 361, 42],
                    [1, 336, 42], [3, 203], [1, 176, 8], [3, 152], [2, 138, 33], [1, 112, 31], [2, 110, 20],
                    [2, 159, 21], [1, 137, 13], [2, 232, 22], [2, 330, 32], [2, 448, 13], [3, 152],
                    [1, 321, 48], [2, 391, 11], [2, 76, 29], [3, 447], [1, 219, 38], [3, 1], [3, 1], [3, 423],
                    [2, 409, 45], [1, 283, 21], [3, 203], [2, 57, 25], [1, 6, 7], [1, 79, 41], [3, 203],
                    [2, 405, 21], [1, 357, 3], [2, 369, 15], [2, 384, 42], [3, 152], [3, 152], [1, 331, 23],
                    [3, 152], [3, 384], [1, 40, 12], [1, 255, 22], [1, 110, 19], [2, 402, 43], [1, 199, 39],
                    [3, 255], [3, 1], [2, 187, 39], [2, 104, 18], [2, 338, 39], [3, 152], [3, 152]]))
